//
//  Problem389.swift
//  LeetCode
//
//  Created by 武侠 on 2023/6/19.
//  Copyright © 2023 zhulongiMac02. All rights reserved.
//

import UIKit

/*
 389. 找不同   简单
 
 给定两个字符串 s 和 t ，它们只包含小写字母。
 字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
 请找出在 t 中被添加的字母。

 示例 1：
     输入：s = "abcd", t = "abcde"
     输出："e"
     解释：'e' 是那个被添加的字母。
 示例 2：
     输入：s = "", t = "y"
     输出："y"
 提示：
 0 <= s.length <= 1000
 t.length == s.length + 1
 s 和 t 只包含小写字母
 */
class Problem389: NSObject {
    /*
     方法一：字典 ✅
     第一遍：遍历字符串s，存储每个字母的个数 + 1
     第二遍：遍历字符串t，删除每个字母的个数 - 1
     第三遍：遍历字典，如果字母个数 == -1，就是该字母
     */
    func findTheDifference(_ s: String, _ t: String) -> Character {
        var dic:[Character: Int] = [:]
        
        var i = s.startIndex
        while i != s.endIndex {
            dic[s[i], default: 0] += 1
            dic[t[i], default: 0] -= 1
            i = s.index(after: i)
        }
        
        let c = t[t.index(before: t.endIndex)]
        dic[c, default: 0] -= 1
        for c in dic.keys {
            if dic[c] == -1 {
                return c
            }
        }
        return dic.keys.first!
    }
    
    /*
     方法二：异或 ✅
     同时遍历2个字符串：因为其他字符都是成对存在的，只有我们想要的支付是独自的，所以同时异或每一个字符，最后剩下的字符就是我们想要的。
     */
    func findTheDifference2(_ s: String, _ t: String) -> Character {
        var ci:UInt8 = 0
        var i = s.startIndex
        while i != s.endIndex {
            ci ^= s[i].asciiValue! ^ t[i].asciiValue!
            i = s.index(after: i)
        }
        
        ci ^= t[t.index(before: t.endIndex)].asciiValue!
        
        return Character(UnicodeScalar(ci))
    }
}
